In recent years, personal computers and digital communication systems have become pervasive in industrialized nations. As well, the speed and power of these systems are now at the point where any subject matter including images, audio, video and software can be stored, transferred and reproduced with ease. Because these systems are digital, the storage, transfer and reproduction can be performed flawlessly; each successive copy of a digital file may be made precisely the same as the original. This is in contrast to analogue systems used in the past, where the quality of each successive copy was poorer than the previous one, and all of the known storage media deteriorated overtime.
Obviously, this ability to copy and transfer digital data with virtually no loss in quality is having a great impact on the revenues of many digital rights holders, including music, movie and software producers. Many techniques for protecting the intellectual property rights of these digital content and software producers have been proposed but have had little success. One technique that has shown particular promise is that of “digital marks”.
Digital marks such as “digital fingerprints” or “watermarks” are patterns of bits (i.e. 0's and 1's) inserted into a digital file, that can be used to identify the file's owner or originator. Unlike printed watermarks, which are intended to be somewhat visible, digital watermarks are designed to be invisible. The actual bits that make up the watermark are also scattered throughout the digital file so that they cannot be identified and manipulated by an attacker.
Digital marks generally serve two basic purposes (see, for example: Protecting ownership rights through digital watermarking, by H. Berghel and L. O'Gorman, 1996, IEEE Computer 29:7, pp. 101-103 and Attacks on copyright marking systems, by Fabien A. P. Petitcolas, Ross J. Anderson, and Markus G. Kuhn, 1998, 2nd Workshop on Information Hiding, LNCS vol. 1525 (isbn 3-540-65386-4), pp. 218-238):    1. Investigative: the owner reads a fingerprint (such as a concealed serial number) to determine how the marked entity (say, a picture in jpeg format) leaked. A trail of marked entities serves the owner in the same way that a trail of fingerprints serves a police detective; so that an owner can identify persons who have purloined the owner's property; and    2. Legal: the owner must prove in court that an infringed data file contains a watermark (a concealed copyright message), and that this watermark is the owner's.
The investigative need is the easier of the two needs to meet, since everything may be kept secret: the owner need reveal nothing about how the mark was applied, and legal proof is not required. That is, there is generally no need to justify the manner in which the thief was identified, since the owner is primarily interested in asserting legal rights over a marked entity in the thief's possession.
However, addressing the legal purpose is sufficiently difficult that some consider it infeasible against a resourceful, clever attacker (see, for example: Protecting digital media content, by Nasir Memon and Ping Wah Wong, 1998, Communications of the ACM 41:7, pp. 34-43).
Greatly exacerbating the difficulty of addressing the legal purpose above is the fact that the first use of a watermark extraction program in a courtroom, based on a particular watermarking method, reveals the watermarking method. After the first legal justification (and hence, revelation) of the method, hostile parties are equipped to remove or damage its watermarks on a permanent basis thereafter.
In order to provide legal watermarking the owner of the watermark would proceed roughly along the lines of the following:    1. employing a watermarking method, embodied in an “injector” implementation which applies the watermark to an owned item (possibly using a secret key) and an “extractor” implementation which reveals the watermark on an owned item (requiring the secret key, if one was used by the injector program);    2. keeping secret the keys (if any) used for watermarking owned items;    3. in court, demonstrating the watermark as follows:            a. revealing the algorithm, so it can be justified as legitimate;        b. loading the extractor and the impugned data/software file to be analysed, and having an agent of the court or a party trusted by the court apply the secret key (if any) to the extractor. Note that the key need not be revealed; and        c. demonstrating that the revelation of the watermark by the (now justified) extractor proves the owner's claim to be the rightful owner of the disputed item containing the watermark.This methodology may be implemented in two major variants:            1. either keeping the injector and extractor algorithms a secret until it is necessary to disclose them during a court proceeding; or    2. publishing the injector and extractor algorithms.
If the injector and extractor algorithms had been kept secure by the owner, then the public disclosure of these algorithms will reduce the level of security that has been enjoyed before the public disclosure. If the watermarking method had already been published, then the attacker would already have had sufficient information to permit compromise of the watermarks the algorithm applies.
There is therefore a need for a watermarking method which allows legal justification of a claim to ownership of a purloined, watermarked entity, without revealing to the world at large the algorithm by which the watermark is applied or revealed.